// 移动零
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int left = 0, right = 0;
        while (right < nums.size())
        {
            if (nums[right] != 0)
            {
                swap(nums[left++], nums[right]);
            }
            right++;
        }
    }
};

// 复写零
class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        // 1.先找到最后一个需要复写的数
        int left = -1, right = 0, n = arr.size();
        while (left < n - 1)
        {
            if (arr[right] == 0) left += 2;
            else left ++;
            // 记得写right++的判断条件
            if (left < n - 1) right++;
        }
        
        // 2.处理特殊情形
        if (left > n -1)
        {
            arr[n - 1] = 0;
            left = n - 2;
            right--;
        }
        
        // 3.从后向前进行复写
        while (left >= 0)
        {
            if (arr[right] != 0) arr[left--] = arr[right];
            else
            {
                arr[left--] = 0;
                if (left >= 0) arr[left--] = 0;
            }
            right--;
        }
    }
};

// 快乐数
class Solution {
    int square_add(int n)
    {
        int sum = 0;
        while (n)
        {
            int count = n % 10;
            sum += count * count;
            n = n/10;
        }
        return sum;
    }
public:
    bool isHappy(int n) {
        // 先写一个求数各位平方和的函数
        // 定义快慢双指针进行求解
        int slow = n, fast = square_add(n);
        while (slow != fast)
        {
            slow = square_add(slow);
            fast = square_add(square_add(fast));
        }
        return slow == 1 ? true : false;
    }
};

// 盛最多的水的容器
class Solution {
public:
    int maxArea(vector<int>& height) {
        // 从最外边界开始求体积
        int left = 0, right = height.size() - 1;
        int v = 0;
        while (left < right)
        {
            v = max(v, (right - left) * min(height[left], height[right]));
            // 更新边界体积
            if (height[left] < height[right]) left++;
            else right--;
        }
        return v;
    }
};
// 有效三角形的个数
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        // 1.先对数组进行排序
        sort(nums.begin(), nums.end());
        // 2.双指针统计三角形个数
        int count = 0;
        for (int i = nums.size() -1; i >= 2; i--)
        {
            int left = 0, right = i - 1;
            while (left < right) // 可别将while循环给漏掉
            {
               if (nums[left] + nums[right] > nums[i]) 
               {
                   count += right - left;
                   right--;
               }
               else left++;
            }
        }
        return count;
    }
};

// 查找价格为目标值的两个商品
class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        int left = 0, right = price.size() - 1;
        while (left < right)
        {
            if (price[left] + price[right] < target) left++;
            else if (price[left] + price[right] > target) right--;
            else return {price[left], price[right]};
        }
        return {-1, -1};
    }
};

// 三数之和
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 对数组进行排序
        sort(nums.begin(), nums.end());
        // 创建vector<vector<int>> 用来储存三元组
        vector<vector<int>> ret;
        int n = nums.size();
        for (int i = 0; i <= n - 3;)
        {
            if (nums[i] > 0) break; // 进行的一个小优化
            int left = i + 1, right = n -1;
            while (left < right)
            {
                if (nums[left] + nums[right] < -nums[i]) left++; // 向右边找大
                else if (nums[left] + nums[right] > -nums[i]) right--; // 向左边找小
                else
                {
                    ret.push_back({nums[i], nums[left], nums[right]});
                    left++, right--;
                    // 开始去重
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right + 1] == nums[right]) right--;
                }
            }
            i++;
            // 对i去重
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
};

// 四数之和
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        // 先对数组进行排序
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        int n = nums.size();
        
        for (int i = 0; i <= n - 4;)
        {
            for (int j = i + 1; j <= n -3;)
            {
                int left = j + 1, right = n -1;
                while (left < right)
                {
                    long long result = (long long)target - nums[i] - nums[j];
                    if (nums[left] + nums[right] > result) right--;
                    else if (nums[left] + nums[right] < result) left++;
                    else
                    {
                        ret.push_back({nums[i], nums[j], nums[left], nums[right]});
                        left++, right--;
                        while (left < right && nums[left] == nums[left - 1]) left++;
                        while (left < right && nums[right] == nums[right + 1]) right--;
                    }
                }
                j++;
                while (j < n && nums[j] == nums[j - 1]) j++;
            }
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
};